#include <vector>
using namespace std;

vector<bool> vi;
vector<bool> col;
bool can = 1;
void dfs(int x, int color, vector<vector<int>>& graph) {
    if (can == 0) return;
    vi[x] = 1;
    col[x] = color;
    for (int nei : graph[x]) {
        if (!vi[nei]) {
            dfs(nei, !color, graph);
        } else {
            if (col[nei] == col[x]) {
                can = 0;
                return;
            }
        }
    }
}

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
    vector<vector<int>> graph(n + 1, vector<int>());
    for (int i = 0; i < dislikes.size(); i++) {
        graph[dislikes[i][0]].emplace_back(dislikes[i][1]);
        graph[dislikes[i][1]].emplace_back(dislikes[i][0]);
    }
    vi.resize(n + 1, 0);
    col.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!vi[i]) dfs(i, 0, graph);
    }
    return can;
}